서로소 아이디얼

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 성질
4. 확률론적 성질
5. 표기법 및 판별
6. 서로소 쌍 생성
7. 응용
8. 일반화
참조

1. 개요

서로소 아이디얼은 정수, 다항식, 환의 아이디얼 등에서 공통 약수가 1 또는 가역원뿐인 경우를 의미하며, 수론 및 대수학에서 중요한 개념이다. 정수의 경우 최대공약수가 1인 두 정수를 서로소라 하고, 모든 쌍이 서로소인 집합을 쌍별 서로소라 한다. 환의 아이디얼에서는 두 아이디얼의 합이 환 전체와 같을 때 서로소라고 정의하며, 중국인의 나머지 정리와 같은 중요한 정리의 가설로 사용된다. 또한, 서로소는 확률론적 성질을 가지며, 기계 설계, 암호학 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

수론 - 타원곡선
타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
수론 - 최소공배수
최소공배수는 둘 이상의 정수들의 공배수 중 가장 작은 양의 정수로서, 소인수분해나 최대공약수와의 관계를 이용하여 구할 수 있으며, 분수 통분이나 기어 회전 수 계산 등 여러 분야에 응용된다.

서로소 아이디얼
정의
정의	두 정수가 공통된 양의 약수를 1 이외에는 가지지 않을 때, 이 두 정수를 서로소(영어: coprime, relatively prime)라고 한다.
기호	와 가 서로소임을 나타내는 기호는 다양하며, 대표적으로 gcd(, ) = 1 또는 ⊥ 가 있다.
성질
정수론적 성질	a와 b가 서로소일 필요충분조건은 ax + by = 1을 만족하는 정수 x, y가 존재한다는 것이다 (베주 항등식). a와 b가 서로소이고 a가 bc를 나누면 a는 c를 나눈다 (유클리드의 보조정리). a와 b가 서로소이면, 임의의 정수 k에 대해 a와 b + ak는 서로소이다. a와 b가 서로소이면 ak와 bl은 임의의 양의 정수 k, l에 대해 서로소이다. 두 정수 a, b에 대해 d = gcd(a, b)라고 하면, a/d와 b/d는 서로소이다.
확률론적 성질	임의로 선택한 두 정수가 서로소일 확률은 6/π² ≈ 61%이다.
일반화
정수 집합	정수들의 집합 S의 모든 원소가 공유하는 양의 약수가 1밖에 없으면, S의 원소들은 서로소라고 한다. S의 모든 두 원소가 서로소이면, S의 원소들은 쌍마다 서로소(pairwise coprime)라고 한다.
아이디얼	환 R의 아이디얼 A와 B에 대해, A + B = R이면 A와 B는 서로소라고 한다.
영어 용어
용어	영어로는 "coprime", "relatively prime", "prime to" 등의 용어가 사용된다. "mutually prime"이라는 용어도 사용되지만, 이는 집합의 원소들이 서로소인 경우에 주로 사용된다.
일본어
용어	일본어로는 "互いに素(타가이니 소)"라고 한다.
한국어
용어	한국어로는 "서로소"라고 한다.

2. 정의

3과 10처럼 모두 나누는 양의 정수가 1뿐인 경우, 이들은 서로소이다. 반면 3과 6은 모두 3으로 나누어지므로 서로소가 아니다. 729와 1000은 1 이외의 공약수가 없으므로 서로소이지만, 729와 1296은 3, 9, 27, 81로 나누어지므로 서로소가 아니다. 1000과 1296 역시 2, 4, 8로 나누어지므로 서로소가 아니다.

서로소 여부는 소인수 분해로 판별할 수 있지만, 유클리드 호제법을 통해 최대공약수를 구하는 것이 더 빠르다.

양의 정수 $n$과 서로소인 ($1$부터 $n$ 사이의) 정수의 개수는 오일러 피 함수 $\varphi(n)$으로 주어진다.

세 정수 $a, b, c$가 서로소라는 것은 $\gcd(a, b, c) = 1$임을 의미한다. $\gcd(a, b) = \gcd(b, c) = \gcd(c, a) = 1$이면, $a, b, c$는 '쌍마다 서로소'(pairwise coprime^영어)이다. 서로소라고 해서 항상 쌍마다 서로소는 아니다. (예: $a = 6, b = 15, c = 10$) 일반적인 $n$개의 정수에 대해서도 같은 방식으로 정의한다.

2. 1. 정수의 경우

정수

n_1, n_2, \dots, n_k

의 최대공약수가 1이면, 이들은 서로소이다. 특히 두 정수

m, n

의 최대 공약수가 1이라면, 이 두 정수는 서로소이다.^[1]

모든 서로 다른 두 정수의 쌍

n_i \ne n_j

이 서로소이면, 정수

n_1, n_2, \dots, n_k

는 '쌍마다 서로소'(pairwise coprime)라고 한다. 쌍마다 서로소는 서로소보다 강한 개념이다.^[1] 예를 들어, 정수 6, 10, 15는 모두를 나누는 양의 정수가 1뿐이므로 서로소이지만,

\gcd(6, 10) = 2

이므로 쌍마다 서로소는 아니다.^[1]

쌍마다 서로소의 개념은 중국인의 나머지 정리와 같이 수론의 많은 결과에서 가설로 중요하다.^[1]

정수의 무한 집합이 쌍별 서로소일 수 있다. 주목할 만한 예로는 모든 소수의 집합, 실베스터 수열의 원소 집합, 모든 페르마 수의 집합이 있다.^[1]

서로소 여부는 소인수 분해를 통해 확인할 수 있지만, 유클리드 호제법을 사용하는 것이 더 빠르다.^[1]

양의 정수

n

과 서로소인 (

1

부터

n

사이의) 정수의 개수는 오일러 피 함수

\varphi(n)

에 의해 주어진다.^[1]

세 개의 정수

a, b, c

가 서로소라는 것은

\gcd(a, b, c) = 1

이 성립하는 것을 의미한다.

\gcd(a, b)

,

\gcd(b, c)

,

\gcd(c, a)

가 모두

1

과 같을 때,

a, b, c

는 쌍마다 서로소이다. 일반적인

n

개의 정수에 대해서도 마찬가지로 정의된다.^[1]

$0$ 과 서로소인 정수는 $1$ 과 $-1$ 뿐이며, 임의의 정수와 서로소인 정수도 $1$ 과 $-1$ 뿐이다.^[1]
서로 다른 두 소수는 서로소이며, 연속하는 두 정수도 서로소이다.^[1]
$2$ 이상의 정수는, 그 (자신을 포함한) 배수나 $2$ 이상의 약수와 서로소가 아니다.^[1]
$a$ 와 $b_1$ , $a$ 와 $b_2$ 가 각각 서로소이면, $a$ 와 $b_1b_2$ 도 서로소이다.^[1]

정수

a, b

가 서로소인 것과 동치인 조건은 다음과 같다.^[1]

$a, b$ 를 함께 나누는 소수가 존재하지 않는다.
$ax + by = 1$ 을 만족하는 정수 $x, y$ 가 존재한다. (베주의 항등식 참조)
$b$ 는 $a$ 를 법으로 하는 역수를 갖는다. 즉, $by \equiv 1 \pmod a$ 를 만족하는 정수 $y$ 가 존재한다. 다른 말로 하면, $b$ 는 $a$ 를 법으로 하는 잉여류 환 $\mathbb{Z}/a\mathbb{Z}$ 의 단원이 된다.
$a, b$ 의 최소공배수 $\operatorname{lcm}(a, b)$ 가 곱 $ab$ 와 같다.
$a, b$ 의 최대공약수 $\gcd(a, b)$ 가 $1$ 과 같다.
$2^a - 1$ 과 $2^b - 1$ 가 서로소이다.

2. 2. 다항식의 경우

체 Field|필드^영어

K

위의 다항식

p_1(x),\dots,p_k(x)\in K[x]

의 최대공약수가 0차 다항식(즉, 1의 약수이자 1의 배수인 다항식)이라면, 이들은 '''서로소'''라고 한다. 모든 서로 다른 두 다항식의 쌍이 서로소라면, 이들은 '''쌍마다 서로소'''라고 한다.^[1]

이 개념은 Zahlring|찰링^de(정수환) 이외의 다른 대수 구조로 확장될 수 있다. 예를 들어, 다항식의 최대공약수가 1인 경우 이를 서로소 다항식이라고 한다.^[1]

2. 3. 환의 원소의 경우

정역

R

의 원소

r_1,\dots,r_k\in R

의 최대 공약수가 가역원(즉, 곱셈 항등원의 약수이자 배수인 원소)이라면, 이들이 '''서로소'''라고 한다. 모든 서로 다른 두 원소의 쌍이 서로소라면, 이들이 '''쌍마다 서로소'''라고 한다.

2. 4. 아이디얼의 경우

환

R

의 아이디얼

\mathfrak a_1,\dots,\mathfrak a_k\subset R

에 대해,

\mathfrak a_1+\cdots+\mathfrak a_k=R

이면, 이들은 서로소이다. 모든 서로 다른 두 아이디얼의 쌍이 서로소이면, 이들은 '쌍마다 서로소'이다.

환

R

의 두 아이디얼

A

와

B

는

A+B=R

일 때 서로소(또는 ''코맥시멀'')라고 부른다. 이는 베주 항등식을 일반화한 것이다. 이 정의에 따르면, 주 아이디얼

(a)

과

(b)

가 정수환

\mathbb{Z}

에서 서로소일 필요충분조건은

a

와

b

가 서로소인 것이다. 환

R

의 아이디얼

A

와

B

가 서로소이면,

AB=A\cap B

이다. 또한,

C

가

BC

를 포함하는 또 다른 아이디얼이면,

A

는

C

를 포함한다. 중국인의 나머지 정리는 서로소 아이디얼을 사용하여 임의의 가환환으로 일반화할 수 있다.

3. 성질

0과 서로소인 정수는 1과 -1뿐이며, 임의의 정수와 서로소인 정수도 1과 -1뿐이다.
서로 다른 두 소수는 서로소이며, 연속하는 두 정수도 서로소이다.
a와 b가 서로소이면, a^k와 b^m도 서로소이다.

다음은 정수 a, b가 서로소인 것과 동치인 조건이다.

a, b를 함께 나누는 소수가 존재하지 않는다.
베주 항등식에 따라, ax + by = 1을 만족하는 정수 x, y가 존재한다.
b는 a를 법으로 하는 곱셈 역원을 갖는다. 즉, by ≡ 1 (mod a)를 만족하는 정수 y가 존재한다.
a와 b의 최소공배수는 ab와 같다.

3. 1. 베주 항등식

두 정수 $m, n \in \mathbb{Z}$에 대하여, 다음 조건들은 서로 동치이다.

$m, n$은 서로소이다.
$m, n$은 공통의 소인수를 갖지 않는다.
(베주 항등식) $um + vn = 1$인 정수 $u, v$가 존재한다.
$(m), (n) \subset \mathbb{Z}$는 서로소이다.

두 다항식 $p(x), q(x) \in K[x]$에 대하여, 다음 조건들은 서로 동치이다.

$p(x), q(x)$는 서로소이다.
$p(x), q(x)$는 공통의 기약 다항식 약수를 갖지 않는다.
(베주 항등식) $u(x)p(x) + v(x)q(x) = 1$인 $u(x), v(x) \in K[x]$가 존재한다.
$(p(x)), (q(x)) \subset K[x]$는 서로소이다.

보다 일반적으로, 환 $R$ 및 그 두 원소 $a, b \in R$에 대하여, 만약 $R$가 유일 인수 분해 정역이라면, 다음 조건들이 서로 동치이다.

$a, b$는 서로소이다.
$a, b$는 공통의 소원 약수를 갖지 않는다.

만약 $R$가 주 아이디얼 정역이라면, 다음 조건들이 서로 동치이다.

$a, b$는 서로소이다.
(베주 항등식) $ua + vb = 1_R$인 $u, v \in R$가 존재한다.
$(a), (b) \subset R$는 서로소이다.

다음 조건들은 $a$와 $b$가 서로소라는 것과 동치이다.

어떤 소수도 $a$와 $b$를 동시에 나누지 않는다.
정수 $x, y$가 존재하여 $ax + by = 1$ (베주 항등식 참조).

3. 2. 중국인의 나머지 정리

유사환의 쌍마다 서로소 아이디얼에 대하여 중국인의 나머지 정리가 성립한다. 정수나 다항식의 연립 합동 방정식의 해의 구조에 대한 명제는 이에 대한 특수한 경우이다.

환 ''R''의 두 아이디얼 ''A''와 ''B''는

A+B=R

일 때 서로소(또는 ''코맥시멀'')라고 부른다. 이는 베주 항등식을 일반화한 것이다. 이 정의에 따르면, 주 아이디얼 (''a'')와 (''b'')가 정수환에서 서로소일 필요충분조건은 ''a''와 ''b''가 서로소인 것이다. 환 ''R''의 아이디얼 ''A''와 ''B''가 서로소이면,

AB=A\cap B

이다. 또한, ''C''가 ''BC''를 포함하는 또 다른 아이디얼이면, ''A''는 ''C''를 포함한다. 중국인의 나머지 정리는 서로소 아이디얼을 사용하여 임의의 가환환으로 일반화할 수 있다.

3. 3. 기타 성질

0과 서로소인 정수는 1과 -1뿐이며, 모든 정수와 서로소인 정수도 1과 -1뿐이다.
서로 다른 두 소수는 서로소이며, 연속하는 두 정수도 서로소이다.
a와 b가 서로소이면, a^k와 b^m도 서로소이다.

다음은 a와 b가 서로소인 것과 동치인 조건들이다.

어떤 소수도 a와 b를 동시에 나누지 않는다.
베주 항등식에 따라, ax + by = 1을 만족하는 정수 x, y가 존재한다.
b는 a를 법으로 하는 곱셈 역원을 갖는다. 즉, by ≡ 1 (mod a)를 만족하는 정수 y가 존재한다.
a와 b의 최소공배수는 ab와 같다.

4. 확률론적 성질

두 정수가 서로소일 확률은 $\frac6{\pi^2}$ (약 61%)이다.

임의의 숫자가 소수(또는 어떤 정수) $p$ 로 나누어질 확률은 $\frac{1}{p}$ 이다.^[16] 예를 들어, 7번째마다 정수는 7로 나누어진다. 따라서 두 숫자가 모두 $p$ 로 나누어질 확률은 $\frac{1}{p^2}$ 이고, 적어도 그 중 하나가 그렇지 않을 확률은 $1-\frac{1}{p^2}$ 이다. 서로 다른 소수와 관련된 가분성 사건들은 상호 독립적이다.^[9]

이러한 추론으로 두 숫자가 서로소일 확률은 모든 소수에 대한 곱으로 주어지며, 다음과 같이 계산할 수 있다.

: $\prod_{p\in\mathbb P}\left(1-\frac1{p^2}\right)=\frac1{\displaystyle{\prod_{p\in\mathbb P}\frac1{1-p^{-2}}}}=\frac1{\zeta(2)}=\frac6{\pi^2}$

여기서 $\mathbb P$ 는 소수의 집합, $\zeta$ 는 리만 제타 함수이다. $\zeta(2)$ 를 $\frac{\pi^2}{6}$ 로 평가하는 것은 레온하르트 오일러가 해결한 바젤 문제이다.^[9]

더 일반적으로, $k$ 개의 임의로 선택된 정수가 집합적으로 서로소일 확률은 $\frac{1}{\zeta(k)}$ 이다.^[16]

5. 표기법 및 판별

두 정수 $a$ 와 $b$ 가 서로소임을 나타내는 표준적인 방법은 $\gcd(a, b) = 1$ 또는 $(a, b) = 1$ 이다.^[3] 로널드 그레이엄, 도널드 커누스, 오렌 파타슈닉은 1989년 교과서 ''구체수학''에서 $a\perp b$ 라는 대안적인 표기법을 제안하기도 했다.^[3]

서로소 여부를 빠르게 판별하는 방법으로는 유클리드 호제법과 그보다 빠른 변형 알고리즘인 이진 최대공약수 알고리즘, 레머의 최대공약수 알고리즘 등이 있다.

6. 서로소 쌍 생성

(2, 1)을 뿌리로 하는 나무. 뿌리 (2, 1)은 빨간색으로 표시되어 있으며, 세 개의 자식은 주황색, 세 번째 세대는 노란색 등으로 무지개 순서로 표시됩니다.

서로소인 양의 정수 쌍 (''m'', ''n'') (''m'' > ''n''인 경우)은 두 개의 서로소인 완전 3진 트리로 배열될 수 있다. 하나는 (2, 1)에서 시작하고 (짝수-홀수 및 홀수-짝수 쌍)^[10], 다른 하나는 (3, 1)에서 시작한다(홀수-홀수 쌍).^[11] 각 정점 (''m'', ''n'')의 자식은 다음과 같이 생성된다.

가지	생성 공식
가지 1	$(2m-n,m)$
가지 2	$(2m+n,m)$
가지 3	$(m+2n,n)$

이 방식은 유효하지 않은 구성원이 없고, 모든 쌍을 포함하며, 중복되지 않는다.

양의 서로소 쌍 (''m'', ''n'') (''m'' > ''n''인 경우)의 트리를 생성하는 또 다른 방법은 두 개의 생성기 $f:(m,n)\rightarrow(m+n,n)$ 및 $g:(m,n)\rightarrow(m+n,m)$ 을 사용하여, 뿌리 (2,1)에서 시작하는 것이다. 결과 이진 트리인 Calkin–Wilf tree는 모든 쌍을 포함하며 중복되지 않는다.

7. 응용

기계 설계에서 균일하고 균등한 기어 마모는 서로 맞물리는 두 기어의 잇수를 서로소로 선택함으로써 달성된다. 1:1 기어비가 필요할 경우, 두 개의 동일한 크기의 기어 사이에 해당 기어와 서로소인 기어를 삽입할 수 있다.^[12]

컴퓨터 이전의 암호학에서 일부 버넘 암호 기계는 서로 다른 길이의 여러 개의 키 테이프 루프를 결합했다. 많은 로터 머신은 서로 다른 수의 이빨을 가진 로터를 결합한다. 이러한 조합은 전체 길이 집합이 쌍별로 서로소일 때 가장 잘 작동한다.^[13]^[14]^[15]

픽스드 기어 자전거의 이상적인 스키드 포인트 설계에서 체인링과 코그의 톱니 수가 서로소이면, 스키드 포인트라고 불리는 타이어가 마모되는 지점은 코그의 톱니 수와 같아진다.

8. 일반화

서로소 개념은 정수뿐만 아니라 다항식, 환의 원소, 아이디얼 등으로 확장될 수 있다.

체 $K$ 위의 다항식 $p_1(x), \dots, p_k(x) \in K[x]$ 의 최대 공약수가 0차 다항식(즉, 1의 약수이자 1의 배수인 다항식)이라면, 이들을 '''서로소'''라고 한다. 모든 서로 다른 두 다항식의 쌍이 서로소라면, 이들이 '''쌍마다 서로소'''라고 한다.

정역 $R$ 의 원소 $r_1, \dots, r_k \in R$ 의 최대 공약수가 가역원(즉, 곱셈 항등원의 약수이자 배수인 원소)이라면, 이들이 '''서로소'''라고 한다. 모든 서로 다른 두 원소의 쌍이 서로소라면, 이들이 '''쌍마다 서로소'''라고 한다.

환 $R$ 의 아이디얼 $\mathfrak a_1, \dots, \mathfrak a_k \subset R$ 가 다음 조건을 만족시키면, '''서로소'''라고 한다.

$\mathfrak a_1 + \cdots + \mathfrak a_k = R$ . 즉, $r_1 + \cdots + r_k = 1_R$ 인 $r_i \in \mathfrak a_i$ 가 존재한다.

특히, 두 아이디얼

\mathfrak a, \mathfrak b \subset R

가

\mathfrak a + \mathfrak b = R

를 만족시키면 서로소라고 한다. 모든 서로 다른 두 아이디얼의 쌍이 서로소라면, 이 아이디얼들이 '''쌍마다 서로소'''라고 한다.

이 개념은 이외의 다른 대수 구조로 확장될 수 있다. 예를 들어, 다항식의 최대공약수가 1인 경우 이를 서로소 다항식이라고 한다.

참조

_[1] 서적 A Treatise on Arithmetic https://archive.org/[...] Thompson, Bigelow & Brown 1872
_[2] 간행물 2008
_[3] 간행물 Concrete Mathematics / A Foundation for Computer Science Addison-Wesley
_[4] 간행물 1988
_[5] 간행물 1966
_[6] 간행물 1966
_[7] 간행물 1966
_[8] 간행물 1992
_[9] 간행물 2008
_[10] 간행물 The family tree of the Pythagorean triplets revisited 1994-07
_[11] 간행물 An alternative characterisation of all primitive Pythagorean triples 2001-07
_[12] 문서 Cryptology: Key Generators with Long Periods https://www.staff.un[...]
_[13] 문서 German Cipher Machines of World War II https://www.nsa.gov/[...] 2014
_[14] 문서 Origins of One-time pad https://www.cipherma[...]
_[15] 문서 Vernam-Vigenère cipher https://www.britanni[...]
_[16] 웹사이트 「 2 整数が互いに素になる確率」の確率論的見方一数値実験による予想の検証一 https://www.kurims.k[...] 京都大学 2024-02-11
_[17] 서적
_[18] 웹인용 http://mathworld.wol[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com